package 回溯;

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 构建字典序最大的可行序列.java
 * @createTime 2023年03月10日 16:33:00
 */
public class 构建字典序最大的可行序列 {
	public static void main(String[] args) {
		System.out.println(constructDistancedSequence(3));
		System.out.println(new BigDecimal(1000).divide(new BigDecimal(100),2, RoundingMode.HALF_UP).toPlainString());
	}

	static Map<Integer, LinkedList<Integer>> timeUsed = new HashMap<>();

	static List<Integer> result = new ArrayList<>();

	public static int[] constructDistancedSequence(int n) {
		backTrace(n, n * 2 - 1, 0);
		int[] ints = new int[n * 2 - 1];
		for (int i = 0; i < result.size(); i++) {
			ints[i] = result.get(i);
		}
		return ints;
	}

	static LinkedList<Integer> list = new LinkedList<>();

	static boolean isOk = false;

	public static void backTrace(int max, int length, int curIndex) {
		if (isOk){
			return;
		}
		//结束条件
		if (length == curIndex) {
			if (!isOk){
				isOk = true;
				result.addAll(list);
			}
			return;
		}
		//遍历循环，从最大的开始循环
		for (int i = max; i > 0; i--) {
			LinkedList<Integer> positionList = timeUsed.getOrDefault(i, new LinkedList<>());
			//如果是1，并且使用过，直接跳过
			if (i == 1 && positionList.size() == 1) {
				continue;
			}
			//条件2校验
			if (positionList.size() == 2) {
				continue;
			}
			//条件3校验
			if (positionList.size() == 1 && Math.abs(positionList.get(0) - curIndex) != i) {
				continue;
			}
			//添加进去
			list.add(i);
			positionList.add(curIndex);
			timeUsed.put(i, positionList);
			backTrace(max, length, curIndex + 1);
			positionList.removeLast();
			list.removeLast();
			timeUsed.put(i, positionList);
		}
	}
}
